package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DivideConquer;
import cn.pugle.oj.catalog.TwoProblem;
import cn.pugle.oj.catalog.Unknown;

import java.util.Arrays;

/**
 * 虽然过了, 但是me: 4 ms, faster than 28.38% of
 * 而且对于{1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 6}这种情况, 时间复杂度不是log(m+n)
 * 差
 * TODO 最优是log(min(m,n))
 *
 * @author tzp
 * @since 2020/10/15
 */
public class LC4 implements DivideConquer, TwoProblem {
    public static class ArrayWrapper {
        public int[] arr;
        public int begin;
        public int end;//exclude

        public ArrayWrapper(int[] arr, int begin, int end) {
            this.arr = arr;
            this.begin = begin;
            this.end = end;
        }

        public ArrayWrapper(int[] arr) {
            this.arr = arr;
            this.begin = 0;
            this.end = arr.length;
        }
    }

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length == 0) return (nums2[(nums2.length - 1) / 2] + nums2[(nums2.length) / 2]) / 2.0;
        if (nums2.length == 0) return (nums1[(nums1.length - 1) / 2] + nums1[(nums1.length) / 2]) / 2.0;

        int a = (nums1.length + nums2.length - 1) / 2;//左mid左边的个数
        int b = (nums1.length + nums2.length) / 2;//右mid左边的个数

        ArrayWrapper smallArr = nums1[0] > nums2[0] ? new ArrayWrapper(nums2) : new ArrayWrapper(nums1);
        ArrayWrapper bigArr = nums1[0] > nums2[0] ? new ArrayWrapper(nums1) : new ArrayWrapper(nums2);
        int leftMid = smallArr.arr[smallArr.begin], rightMid = 0;//防止初始情况a==0
        while (b > 0) {
            int i = Arrays.binarySearch(smallArr.arr, smallArr.begin, smallArr.end, bigArr.arr[bigArr.begin]);
            if (i < 0) {
                i = -i - 1;
            } else {
                i = i + 1;
            }
            int cutNums = i - smallArr.begin;
            if (a > 0) {
                if (cutNums > a) {
                    leftMid = smallArr.arr[smallArr.begin + a];
                } else if (cutNums == a) {
                    leftMid = bigArr.arr[bigArr.begin];
                }
            }
            if (cutNums > b) {
                rightMid = smallArr.arr[smallArr.begin + b];
            } else if (cutNums == b) {
                rightMid = bigArr.arr[bigArr.begin];
            }
            a = a - cutNums;
            b = b - cutNums;
            //swap
            smallArr.begin = i;
            if (smallArr.begin >= smallArr.arr.length) {//找完了.
                if (a > 0) leftMid = bigArr.arr[bigArr.begin + a];
                if (b > 0) rightMid = bigArr.arr[bigArr.begin + b];
                break;
            }
            ArrayWrapper tmp = smallArr;
            smallArr = bigArr;
            bigArr = tmp;
            System.out.println("swap");
        }
        return (leftMid + rightMid) / 2.0;
    }

    public static void main(String[] args) {
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1, 2, 3}, new int[]{4, 5}));
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1}, new int[]{2, 3, 4}));
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1}, new int[]{2}));
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1, 1}, new int[]{1, 1}));
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1, 3}, new int[]{2}));
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1, 3}, new int[]{2, 4}));
//        System.out.println(new LC4().findMedianSortedArrays(new int[]{1, 2, 3, 9}, new int[]{4, 5}));
        System.out.println(new LC4().findMedianSortedArrays(new int[]{1, 2, 3, 4, 5, 6}, new int[]{1, 2, 3, 4, 5, 6}));
    }
}
